package T3;

import com.sun.org.apache.xalan.internal.xsltc.dom.SortingIterator;
import sun.java2d.pipe.SpanIterator;

import java.math.BigInteger;
import java.security.cert.X509Certificate;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 马拉圈
 * Date: 2023-04-17
 * Time: 10:30
 */
public class Day25 {

    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextBigInteger()) {
            BigInteger bigInteger = scanner.nextBigInteger();
            String str = bigInteger.toString();
            long sum = 0;
            do {
                sum = 0;
                for (int i = 0; i < str.length(); i++) {
                    sum += str.charAt(i) - '0';
                }
                str = String.valueOf(sum);
            }while(sum / 10 != 0);
            System.out.println(sum);
        }
    }






    public static Map<Integer, String> map = new HashMap<Integer, String>() {
        {
            BigInteger flag1 = BigInteger.valueOf(1);
            BigInteger flag2 = BigInteger.valueOf(2);
            put(1, analysis(flag1));
            put(2, analysis(flag2));
            for (int i = 3; i <= 10000; i++) {
                BigInteger tmp = flag2;
                flag2 = flag2.add(flag1);
                flag1 = tmp;
                put(i, analysis(flag2));
            }
        }
    };
    public static String analysis(BigInteger n) {
        String str = n.toString();
        StringBuilder stringBuilder = new StringBuilder();
        int len = str.length();
        for (int i = 4; i >= 1; i--) {
            if(len - i >= 0) {
                stringBuilder.append(str.charAt(len - i));
            }else {
                stringBuilder.append(0);
            }
        }
        return stringBuilder.toString();
    }
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt()) {
            int n = scanner.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = scanner.nextInt();
            }
            for (int i = 0; i < n; i++) {
                System.out.print(map.get(arr[i]));
            }
            System.out.println();
        }
    }


    public static int transfer(int n) {
        if(n <= 2) {
            return n;
        }
        int flag1 = 1;
        int flag2 = 2;
        for (int i = 3; i <= n; i++) {
            int tmp = flag2;
            flag2 = (flag1 + flag2) % 10000;
            flag1 = tmp;
        }
        return flag2;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt()) {
            int n = scanner.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = scanner.nextInt();
            }
            for (int i = 0; i < n; i++) {
                System.out.printf("%04d", transfer(arr[i]));
            }
            System.out.println();
        }
    }






}
